/*------------------------------------------------------------------------
*
* geqo_recombination.c
* 其他重组程序
*
* src/backend/optimizer/geqo/geqo_recombination.c
*
*-------------------------------------------------------------------------
*/

/* 贡献者：
   =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
   *  Martin Utesch				 * 自动控制研究所		   *
   =							 = 矿业与技术大学 =
   *  utesch@aut.tu-freiberg.de  * 德国弗赖贝格				   *
   =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
 */

/* -- 这部分的内容改编自 D. Whitley 的 Genitor 算法 -- */

#include "postgres.h"

#include "optimizer/geqo_random.h"
#include "optimizer/geqo_recombination.h"


/*
 * init_tour
 *
 * 随机生成一个合法的“旅行推销员”巡演
 * (即每个点仅访问一次。)
 */
void init_tour(PlannerInfo *fc_root, Gene *fc_tour, int fc_num_gene)
{
	int			fc_i,
				fc_j;

	/*
	 * 我们必须用 1 .. num_gene 的随机排列填充 tour[] 数组。
	 * 我们可以使用 Fisher-Yates 洗牌算法的“内部到外部”变体在一次遍历中完成。
	 * 理论上，我们将每个新值附加到数组中，然后与一个随机选择的
	 * 数组元素（可能包括自身，否则我们无法生成
	 * 最后一座城市在最后的排列）。交换步骤可以通过
	 * 与插入结合来优化。
	 */
	if (fc_num_gene > 0)
		fc_tour[0] = (Gene) 1;

	for (fc_i = 1; fc_i < fc_num_gene; fc_i++)
	{
		fc_j = geqo_randint(fc_root, fc_i, 0);
		/* i != j 检查避免提取未初始化的数组元素 */
		if (fc_i != fc_j)
			fc_tour[fc_i] = fc_tour[fc_j];
		fc_tour[fc_j] = (Gene) (fc_i + 1);
	}
}

/* city table is used in these recombination methods: */
#if defined(CX) || defined(PX) || defined(OX1) || defined(OX2)


/* alloc_city_table
 *
 *	为城市表分配内存
 */
City *
alloc_city_table(PlannerInfo *fc_root, int fc_num_gene)
{
	City	   *fc_city_table;

	/*
	 * palloc 一个额外的位置，以便可以直接索引编号为 1..n 的节点；
	 * 0 将不被使用
	 */
	fc_city_table = (City *) palloc((fc_num_gene + 1) * sizeof(City));

	return fc_city_table;
}

/* free_city_table
 *
 *	  释放城市表的内存
 */
void free_city_table(PlannerInfo *fc_root, City * fc_city_table)
{
	pfree(fc_city_table);
}

#endif							/* CX || PX || OX1 || OX2 */
